COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASI30\M3BASB30\M4NGR40
C00046 00003	
C00047 ENDMK
C⊗;
\\M1BASL30;\M2BASI30;\M3BASB30;\M4NGR40;
\F4
\CThe Bankruptcy of BASIC\F1
\C\F2(A draft)

\F1\C John R. Allen
\C The LISP Company
\C Box 487, Redwood Estates
\C 95044
\J
\F1I predict that the current trends utilizing programming
languages like BASIC
at the  expense of abstraction will have a serious 
impact on the creativity of the next generation of high school and
and college graduates.

I surmise that the New 
Mathematics program met resistance because it was too abstract and short-changed
intuition. 

I believe that  computer science has now matured to the extent that it can
offer an
intermediate position to the two above extremes.
I believe that
this position 
--based on a few fundamental principles of computation-- can be developed
into a viable and exciting program that will teach the \F2substance\F1 of 
computing rather than dwelling on the \F2form\F1 of specific programming languages.
These fundamentals of computation  are 
easier to present  and understand
than  contemporary  programming languages due to their pre-occupation with syntax
and shortsighted view of data structures. 


The approach  I am advocating is based on a  notation/language named LISP whose
foundations are
based on mathematical principles
as  well-founded as those of sets and functions, yet whose
programs
can be executed by a computer.
Furthermore from a practical
standpoint, LISP is the language most commonly used in Artificial Intelligence
work; these AI applications and the techniques they embody offer an incredibly
rich source of examples and insight into the non-mathematical aspects of computing.


LISP, with its dual role as mathematical formalism and
advanced programming language, offers unique
opportunities to those who are first encountering computing. The point of this
note is to sketch some of those benefits, and in the process show how a language
like BASIC shortchanges one's view of computing.


Consider the following quote:

\F2"... it is important not to lose sight of the fact that there is a difference
between training and education. If computer science is a fundamental discipline,
then university education in this field should emphasize enduring fundamental
principles rather than transient current technology."

\F1Peter Wegner        \F2Three Computer Cultures,\F11970.


The "Three 
Cultures" referred to in this quote 
are: Computer Mathematics (applications
in traditional mathematics that can profitably apply computers); Computer
Technology (the engineering and physical aspects surrounding  the realization
of computing devices), and Computer Science (the study of computing). It is a
useful separation of the scientific aspects and ramifications of computers.

Computer Technology is well understood in the Silicon
Valley; it this the art and science
of building the physical devices: applied physics and engineering.
Computer Mathematics is the art and science of using the tools in mathematics: 
applied mathematics.
Computer Science? It is the study of computation, and programming is \F2applied\F1
computation!

Returning to the body of the quotation,
the necessity to emphasize  "fundamental principles" is not the sole 
responsibility of the universities.
Many of one's educational goals 
and expectations are established in high school; it is therefore most important 
that one's introduction to any subject be as faithful to that discipline as
teaching and technology allow. Most subject areas have a well-developed
historical perspective that supports their curricula. Computer science  is a 
relatively young field in the technological domain, but its roots 
are well-founded in mathematics. 

One objective of this note is to demonstrate that an appropriate
blend of traditional mathematics and foundational computing offers substantial
advantages for both programs. One concern I have with the current approach 
is that \F2both\F1 programs may suffer; mathematics may become (even more)
equated with "deep, but irrelevant", and computing be equated with "shallow,
but a good career". Mathematics programs have had to deal with this phenomenon
for years --dwindling enrollments  in University programs are common. The
phenomenon has even more drastic  economic potential in the computing field:
an oft-quoted statistic for the useful lifetime of computer science knowledge
is five years! Surely the result of teaching technology, not fundamentals.
The result is stagnant engineering or expensive retraining to keep up.
No wonder
one sees editorials and articles decrying the diminishing
productivity rate in our computing field, while pointing to Japan's and Europe's
superior performance. Both the French and
 Japanese have a strong interest in foundational computing.
It is time to turn things around in this country, and the place to begin is in the
high schools.

My comments apply both to courses  that expect
their attendees to go on to university education and it applies to programs
that
are to give the general populace an understanding of what
computing is about and how it will impact on their lives: the important
area called "computer literacy." 
In neither case will a technology-driven curricula suffice; the next five years
will see inexpensive computing systems with the power of today's research
machines, tied together through high-speed networks, being accessed  through
highly interactive graphical techniques. 
Several important and innovative projects
are underway now to address these issues: the LOGO project at MIT, the Smalltalk
project at Xerox.  A cursory  knowledge about
how a computer works coupled with  an introduction to BASIC
won't prepare people to cope with these systems (since both systems  are
targeted as educational tools, perhaps we should expect to see  another "parental
backlash" like that experienced with the New Math program).


Further concern is the effect of inaccurate or inadequate information
on those  who plan to continue in a university.
First, I surmise that many  bright people are  put-off by the
patch-work appearance of computing and opt for disciplines that show more substance.
If computer science is to prosper, these individuals must be  attracted.
Second, 
there are severe problems even for those who do  enter a
computer-related
career. Questions are being raised  about the "effect of one's  first
programming language"; it is a real concern. The expressivity and style 
that one develops with their first language has long-term effect. This 
holds for natural language as well as artificial. The  lessons that one
learns from BASIC about structure of algorithms and data are hard to 
overcome. A colleague of mine (a professor at Santa Clara University)
can give  first-hand testimony about the difficulties involved in teaching
people to unlearn misconceptions about  computing. The  department policy
has been to use a "structured" form of Fortran and Pascal as the vehicle.
Both of these languages support  modern techniques for expressing algorithms.
Those who have BASIC experience find it difficult to assimilate 
these ideas into their  programming style while novices suffer no such handicap.

Please 
note: the point is \F2not\F1 to teach a programming language; the point is to
teach about computing and, in the process, teach people to think.
Of course, we need \F2some\F1 notation for giving precise
descriptions  of our concepts, but the notation should not become the
object of study. Compare:

\F2"Mathematical notation is always introduced [in context as needed] rather
than being taught, as programming languages commonly are, in a separate
course. Notation suited as a tool of thought in any topic should permit
easy introduction in the context of that topic."\F1

Ken Iverson \F2Notation as a Tool of Thought\F1 1979 Turing Award Lecture

As "tools of thought", most programming languages fail miserably.
Their design is overly constrained by considerations related to their
execution on contemporary computers; as a result
they fall  short in satisfying
in the criteria by which  notations have traditionally been judged. 

Iverson suggests that in the past, notations have succeeded or 
failed on considerations like the following:

\F3Ease of expressing constructs arising in problems\F1

\F3Suggestivity\F1

\F3Ability to subordinate detail\F1

\F3Economy\F1

\F3Amenability to formal proofs\F1

The first three considerations are related; expressions in
the notation must embody the problem statement in such a way that 
the intellectual burden in manipulating the notation is less than that
involved with the informal conception of the problem. Manipulation of the notation
must aid the solution of the original problem as well as 
support the generalization of results. 


The notion of economy  means that one can explain the
principles 
of the notation from a few basic concepts and rules. For example,
number theory can  be build from the primitives of the number zero, 
equality relation, the operation
of "adding one", and recursion. LISP has a similar foundation. Building from 
the notion of sequence and  equality, with
four primitive operations and recursion one can construct
both the theoretical and the programming structures of LISP.
The effect is to supply the learner with a simple, easily grasped system that
can be expanded and elaborated  as familiarity increases. The pedagogical
benefits in such an approach are substantial.

The notion of  proof has been a main-stay in the history of mathematics.
Its application in science and parts of mathematics has been informal, but
is always grounded on logical foundations that would support formal argument.
A computational notation must \F2at least\F1 do as well.

To the
traditional notational concerns we must add two computer-age ones:

\F3The notation must be executable

The notation should be easy for a machine to manipulate\F1

Surely, if the notation  is to be usable  as a programming language it
must be implementable on a machine and the expressions that one writes in the 
notation must be executable in an unambiguous fashion and must
be computable in finite time.

The second point is overlooked in almost every programming language design.
We see languages that completely ignore the issue of manipulation
of programs (Fortran and Algol); we see
languages that allow the  manipulation of programs as strings (Snobol and BASIC);
we see languages that allow manipulation as character arrays (APL). Yet
programs are none of these objects. 
Programs  are structured objects with interrelated
parts and pieces. Programs that manipulate these representations (like 
compilers) must be able to manipulate these representations in meaningful ways.
To this date, LISP is the only notation that supports a representation of 
programs 
with the theoretical benefits that allows mathematical
discussion  while supporting the practical concerns that are required to 
write complex programs.


In summary,
we \F2must\F1 identify and teach principles  of computation and in that context
one must introduce a notation. That notation must embody these
principles in such a way that one can reason about statements
made in that notation much like one carries on
sustained analysis in mathematical disciplines. 
Furthermore,
that notation must be executable
on a machine in an unambiguous fashion.
We believe that the underlying structure of LISP supplies such principles.
The remainder of this note argues this case.


To begin, a useful distinction between mathematics and computer science
is: mathematics stresses "function" and  and computer science stresses
"algorithm" --one
can argue that set-theoretic ideas are more primitive than functionality, 
but I am  not concerned
with minimality arguments.
Regardless of one's starting point, the idea of
"function" is more abstract than  the idea of "algorithm".
The essential distinction
being that a function definition gives an (implict or explict) rule of 
correspondence while an algorithm  gives an explicit \F2computational\F1
method for calculating those correspondences: there are many algorithms
that will compute the same function.
One way to understand "functionality"
is to view a realization of a function as an algorithm. 

At the introductory level, moving from function to algorithm can have substantial
benefit. An algorithm is a  concrete  recipe and, given a computer,
one can execute the algorithm, reinforcing one's confidence in the  process.
It is important that introductory concepts
have a strong intuitive real-world component; 
later, one can abstract from algorithm to function by presenting two algorithms
that compute the same function and explore what that means.
\.

For example, consider the  following example of functional notation:

	f(x,y) = x*y - 3*x.
\J
When asking "what is the value of f(1,2)?"  we  note that it doesn't matter
whether x*y is evaluated before 3*x; that is, f expresses a \F2functional\F1
relationship, and any rule of computation (obeying certain precedence conventions)
will suffice. I strongly suspect that one teaches (and learns) the evaluation
of such expressions algorithmically, only abstracting to the functional 
level much later, if ever.

To motivate the function versus algorithm distinction,
consider the factorial function, defined for non-negative integers:
\.

	0! = 1 
	n! = n*(n-1)! if n is greater than 0.

\J
which says, "given a non-negative integer, if it is zero, the value is 1;  
otherwise
the value is that integer multiplied by the factorial function operating on
the integer-minus-1."
 
or... "given an integer, call it n. If n is zero the answer expected is 1, otherwise
the expected answer is n multiplied by the factorial function operating on n-1."

or... combining with functional notation,
\.

	factorial(n) = \F2if\F1 n=0 \F2then\F1 1
			           \F2else\F1 n*factorial(n-1)

\P
Now consider:

	fun(x,y) = \F2if\F1 x=0 \F2then\F1 y
			       \F2else\F1 fun(x-1,x*y)
\J

take a moment to look at fun and then  consider the values of fun(1,1),
fun(2,1) and fun(3,1), for example.

Would you like  to conjecture that  fun(x,1) has the
same value  as factorial(x), for every integer x? How would you convince someone
of that conjecture? Write each in a programming notation  and run them on a machine
for many values of x? That's certainly a start: for if the conjecture was false
you might discover a mis-match. But that technique is no proof if the conjecture
is true. It requires proof. 

Indeed, the equivalence of these definitions can be proved.
What does this mean? it says
 we have two algorithms that compute the same function. 
The proof technique is essentially
mathematical induction. 
In fact such proofs are an elegant way to motivate induction, and
a lot more of computing --for the definitions  given above are called recursive
definitions, an elegant formalism analogous to our goal/sub-goal problem solving
intuition. 

The  equations listed above are, in fact,  a form of LISP.
 In LISP, one uses 
recursive definitions as programming language constructs to
write elegant well-structured programs. 
Furthermore, one can prove properties of LISP programs using mathematically
valid principles.
Finally, one can combine the theory with the practice and
can write LISP
programs that would take  two definitions as input, use the
formal rules for program manipulation, and automatically
prove the equivalence of these two definitions.

It is this last area, the manipulation of LISP programs by other LISP programs
that accounts for much of LISP's power: to be able to compute with
data one must represent it in a computer; traditionally we have made our data
fit into numeric quantities   or arrays 
of numbers or characters. LISP frees us from
these restrictions, allowing us to compute with sequences whose elements can be
other sequences or simply symbolic names. Intellectually, 
the shift makes
it much easier to represent and manipulate complex information; that is the business
of Artificial Intelligence in particular, and intelligence in general.

The key to this flexibility and liberation of thinking was LISP's use of the
sequence (or list) as its underlying data representation.
In LISP, a sequence is something like (A, B, (C, D)). This  sequence has three
elements, the third being a sequence itself. Since the commas just get in the
way, we drop them:  (A B (C D)).

For example, to input the fun algorithm to our program-equivalence prover we would
write:
\.

     (DEFINE FUN (X Y) 
			(IF (EQ X 0)
			    Y
			    (FUN (MINUS X 1) (TIMES X Y))))


\J
The syntactic transformation from "fun" to "FUN" is simple --essentially replacing
functional notations like 
\.

	f(x, y, g(z))  by

	(F X Y (G Z)), but

\J
the transformation is a powerful one from the perspective of our prover. 
Such programs must be able to select, compare, and manipulate data structures
that represent subexpressions of algorithms like "fun". 
In the representation, a
subexpression is either an "atomic symbol" or a sequence itself;
and any sequence represents a  functional application, with the first
element of the sequence giving the name of the applied function.
Given  this sequence representation and the operations to manipulate 
sequences, the task of writing complex programs becomes much more manageable.

For example, language processors  (like interpreters
and compilers) initially process   language statements into 
an internal  tree-like representation. They do this
because these tree-structures are  an efficient form 
 of the program for further processing.
Since LISP's sequence notation has a natural representation as a tree
structure it becomes quite easy to write compilers in LISP.
For example, a rather good LISP compiler can be concisely described on 
one 8-1/2 x 11 page; can be easily explained and read; and can be proven correct.
Since  the  transformation  is so simple and yet so powerful, LISP programs
are usually expressed directly in this sequence representation and executed in this
form.

Languages that offer
only numeric or string objects do not supply sufficient flexibility
for complex processsing of structures; therefore
the programmer must create lower-level representations for the needed tree-like
abstractions. The result is a much less readable and more complex program.

In BASIC, this complexity permeates the programming process.
Consider, for example, the Towers of Hanoi puzzle: given three vertical rods
and a stack of discs on one rod, arranged by size such that the largest is
on the bottom; move the discs to the adjacent rod, subject to the constraints that
only one disc may be moved at a time, and no disc may be placed on top of a
smaller disc.

Here is a LISP solution.
\.

hanoi(n, source, destination, spare) <=
		\F2if\F1 n=1 \F2then\F1 move(source, destination)
				\F2else\F1  hanoi(n-1, source, spare, destination)
					move(source, destination)
					hanoi(n-1, spare, destination, source)

Here is a BASIC solution from the March 1980 issue of BYTE Magazine:

010 REM Declare the stack arrays.
020 DIM S$(15),D$(15),I$(15)
030	PRINT
040	PRINT "Number of disks"
050	INPUT P
060	REM if P is too large or too small, STOP
070	IF(P>15) THEN 170
080	IF(P<1) THEN 170
090	REM move P disks from Left to Right
100	LET S$(P)="L"
110	LET D$(P)="R"
120	LET I$(P)="C"
130	REM move those disks!
140	GOSUB 180
150	REM Since that was so much fun let us do it again
160 GOTO 30
170 STOP
180	REM This is the recursive HANOI procedure
190	REM If P=1, move  one disk from source to destination
200	IF(P>1) THEN 230
210	   PRINT "Move a disk from ";S$(P);"to";D$(P);"."
220	RETURN
230	   REM else, move P-1 disks from Source to Intermediate
240		LET P=P-1
250	 	LET S$(P)=S$(P+1)
260		LET D$(P)=D$(P+1)
270		LET I$(P)=I$(P+1)
280		GOSUB 180
290	   REM Move one disk from Source to Destination
300		PRINT "Move a disk from ";S$(P+1);"to";D$(P+1);"."
310	   REM Move P-1 disks from intermediate to Destination
320	 	LET S$(P)=S$(P+1)
330		LET D$(P)=D$(P+1)
340		LET I$(P)=I$(P+1)
350		GOSUB 180
360	   LET P=P+1
370	RETURN
380 END
	

\J
Even translating the LISP solution into  its sequence representation, we still
have a more understandable program than that displayed by BASIC:
\.

(DEFINE HANOI (N SOURCE DESTINATION SPARE)
	(IF (EQ N 1) (MOVE SOURCE DESTINATION)

	       (HANOI (SUB1 N) SOURCE SPARE DESTINATION)
	       (MOVE SOURCE DESTINATION)
	       (HANOI (SUB1 N) SPARE DESTINATION SOURCE)))

with

(DEFINE MOVE (S D) (PRINT "Move disk from" S "to" D))

to print the result on the terminal

and a call:

(HANOI 22 "first" "second" third")

to begin execution

\J
The solutions can be contrasted on several levels. In the BASIC solution,
(line 20) one must prescribe the number of disks that the program will
manipulate; of course, most other programming languages also require this 
declaration. However, such  information is totally irrelevant to the
description (and correctness) of the algorithm; LISP requires no such declarations.
Many LISP systems \F2allow\F1 declarations to aid the programmer
in maintaining consistency, and to aid the compiler when compiling code, but
the LISP definition will execute quite handily without declarations.

Further criticism can be raised concerning the GOSUB construct. The BASIC
program maintains that GOSUB 180 is a call on the Hanoi procedure. That is not
at all clear from the text; "180" is not "Hanoi", and it is not at all obvious
what "180" is operating on as data. The  LISP definition, with its
nmeumonic names and explicit parameters, makes it clear
which function is being called and what objects it operates on.
One may also ponder what has happened to the recursive algorithm when it was
encoded in the BASIC solution

These last two issues --
"180" versus "Hanoi" and the destruction of the recursive 
formulation--  exemplify the issue of "abstraction": the 
abstract, or high-level description of 
algorithms. The LISP solution is more abstract in that it directly expresses
the relationships between consecutive steps, while not requiring unnecessary
specifications of implementation details. Convincing oneself of the correctness
of the LISP formulation is a much easier task than that of convincing oneself
of the correctness of the BASIC program.


Besides LISP's flexible algorithmic expressibility, 
an integral part of LISP's 
power derives from  its ability to  define and manipulate data abstractly.
This means that one can write LISP algorithms that manipulate data
without regard for the implementation details of the data. 
In LISP one can define and  manipulate "abstract objects". The objects
are abstract in that they are described by their behavior, not by their
implementation. Objects are characterized by 
functions called "testers", "selectors",
and "constructors". One can test an object for specified properties; one
can select components from (appropriately tested) objects, and given
a collection of objects, one can create new objects.

These ideas of abstract objects, manipulated
by algorithms  using testers, selectors, and constructors, are at the heart of 
modern computer science. 

Most programming languages have
great difficulty with this  concept
of abstraction. Either the language fails to support an appropriate set
of component data types (Fortran, Algol, Basic, APL) or fails to  support
the interrelating of components at a high  level (PL/1 and Pascal pointers).
The effect is the same: one loses the notation to the strictures of implementation.


An essential problem stems from the  failure to recognize
that \F2programming languages are essentially notations\F1. As notations,
their first concern must be  expressibility of thought. Therefore, a high-level
language's  primary benefit (over machine language) is \F2notational\F1
not \F2computational\F1. The development cycle of most programming 
languages has been driven by computational (implementation) considerations
rather than by notational considerations. 
Languages driven by implementations include Fortran, Basic, and to 
some 
extent Algol. Languages driven by notation include LISP, APL, LOGO, and Smalltalk.

So, at one level, we agree with the "hands-on" algorithmic approach
contained within the computer-oriented educational philosophy. Our disagreement
is not with the instrument, but in the way it is being applied or "played".
One objection stems from the emphasis on performance without an appropriate
view of the instrument itself. The typical computing application is exactly
that: "an application", not an introduction to \F2computing\F1.
The essence  of
Computing is the study of algorithms, not applications.
I do not even advocate  teaching LISP as a programming language, per se: that's
only moving from the "slide rule" to the "hand calculator". 

Mechanical techniques, like the slide rule (in mathematics)
and \F2any specific\F1 programming language (in computer science) 
are inappropriate  vehicles for
teaching principles. The slide rule was only a tool (transient technology),
applying principles of mathematics. A programming language is a tool, applying the
principles of computing.
It is the fundamental
ideas that are important, and those are much more easily presented in the LISP
model  than in the BASIC model.  As a "consumer" language, BASIC is no more
obnoxious than Saturday morning cartoons; as a medium  for teaching people
about the elegance  of computing, it is deadly. 
It shortchanges one's intellect; its expressivity and
style are extraordinarily primitive. I fear we will discover that we have
created a generation of "consuming programmers", able to read (execute)
other people's programs but   unable to write (create) effectively because they
do not understand the principles.

There are several ingredients that contribute to  a creative endeavor
besides  an expressive
language, a fluent author, and an inquisitive mind. One must also have appropriate
working conditions. Though many BASIC's do have interactive features, their
scope is limited. In this area of interactive programming, LISP excells. 
In its role as the implementation language for Artificial Intelligence 
research, LISP systems have acquired an impressive array of program development
tools. There is an important practical lesson to be gained from using such 
tools, much like the liberation of expression one feels on moving from 
pencil-and-paper  to a good text editor. This mode of communication with a  
computer is at the heart of the LOGO/Smalltalk enterprises; these tools
aid substantially in making the program-creation process a pleasant and
rewarding experience. The immediate feedback of interactive computing, coupled
with an "economic" (see earlier comments)  notation, results in a very effective
pedagogical tool.

Clearly I cannot adequately cover  a topic as deep and varied LISP in only a few
pages. I have said little about the  interactive development style  and
programming environments that LISP lends itself to,
and I have said  little about the kinds of applications
that  has made LISP the major tool of AI.
I am preparing 
a more detailed version of this paper  that will address
these issues, however I feel these foundational issues are
the most  critical. I  am  most interested in your
reaction to this draft, and
hope some of the ideas presented here are valuable to you.
\.